package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

import java.util.*;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 二叉树的垂序遍历 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            TreeNode root = TreeNode.init(new ArrayList<>(Arrays.asList(1,2,3,4,6,5,7)));
            List<List<Integer>> lists = solution.verticalTraversal(root);
            for (List<Integer> list : lists){
                System.out.println(Arrays.toString(list.toArray()));
            }
        }
        class Triple {
            TreeNode node ;
            int col,row;

            public Triple(TreeNode node, int row,int col) {
                this.node = node;
                this.col = col;
                this.row = row;
            }
        }
        ArrayList<Triple> nodeList = new ArrayList<>();
        public List<List<Integer>> verticalTraversal(TreeNode root) {
            // 遍历二叉树，并且为所有节点生成对应的坐标
            travel(root, 0, 0);
            // 对节点排序
            Collections.sort(nodeList,(Triple a,Triple b)->{
                // 根据题意，根据坐标值对所有节点进行排序：
                // 如果 col 和 row 都相同，按照 node.val 从小到大排序。
                if (a.col == b.col && a.row == b.row){
                    return a.node.val-b.node.val;
                }
                // 按照 col 从小到大排序，col 相同的话按 row 从小到大排序，
                if (a.col == b.col){
                    return a.row - b.row;
                }
                // 按照col从小到大排序
                return a.col - b.col;
            });
            // 将排好序的节点组装成题目要求的返回格式
            LinkedList<List<Integer>> res = new LinkedList<>();
            // 记录上一列编号，初始化一个特殊值
            int preCol = Integer.MIN_VALUE;
            for (int i = 0; i < nodeList.size(); i++) {
                Triple cur = nodeList.get(i);
                if (cur.col != preCol) {
                    // 开始记录新的一列
                    res.addLast(new LinkedList<>());
                    preCol = cur.col;
                }
                res.getLast().add(cur.node.val);
            }

            return res;
        }

        public void travel(TreeNode root, int row, int col) {
            if (root == null) return;
            // 添加到列表里面
            nodeList.add(new Triple(root, row, col));
            // 添加左右子树
            travel(root.left, row + 1, col - 1);
            travel(root.right, row + 1, col + 1);
        }
    }
}
